package com.jyl.dc;

/**
 * 最大子数组和
 * @ClassName Practice053
 * @Author admin
 * @Date 2024/6/15
 */
public class Practice053 {

    public static void main(String[] args) throws Exception {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int max = maxSubArray(arr);
        System.out.println(max);

        int[] arr1 = {5,4,-1,7,8};
        System.out.println(maxSubArray(arr1));

        int[] arr2 = {1};
        System.out.println(maxSubArray(arr2));

    }

    public static int maxSubArray(int[] nums) {
        return maxSubArray(nums,0,nums.length -1);
    }

    private static int maxSubArray(int[] nums, int start, int end) {
        if (start >= end) {
            return nums[start];
        }

        int mid = (start + end) / 2;

        // 处理对应的三种情况
        int leftMax =  maxSubArray(nums, 0, mid);
        int rightMax = maxSubArray(nums, mid + 1, end);
        int crossMax = getCross(nums,start,mid,end);

        return Math.max(crossMax,Math.max(leftMax,rightMax));
    }

    private static int getCross(int[] nums, int start, int mid, int end) {

        int leftSum = 0;
        int leftSumMax = Integer.MIN_VALUE;
        for (int i = mid; i >= start ; i--) {
            leftSum += nums[i];
            leftSumMax = Math.max(leftSumMax,leftSum);
        }

        int rightSum = 0;
        int rightSumMax = Integer.MIN_VALUE;
        for (int j = mid + 1; j <= end; j++) {
            rightSum += nums[j];
            rightSumMax = Math.max(rightSumMax,rightSum);
        }

        return leftSumMax + rightSumMax;
    }


}
